//给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
//
//
//
// 示例 1：
//
//
//输入：head = [1,2,2,1]
//输出：true
//
//
// 示例 2：
//
//
//输入：head = [1,2]
//输出：false
//
//
//
//
// 提示：
//
//
// 链表中节点数目在范围[1, 10⁵] 内
// 0 <= Node.val <= 9
//
//
//
//
// 进阶：你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
// Related Topics 栈 递归 链表 双指针 👍 1254 👎 0

package leetcode.editor.cn;

import com.sicheng.algorithm.node.ListNode;

import java.util.ArrayDeque;

@SuppressWarnings("all")
//Java：回文链表
public class 回文链表 {
    public static void main(String[] args) {
        Solution solution = new 回文链表().new Solution();
        // TO TEST
    }
//leetcode submit region begin(Prohibit modification and deletion)

    /**
     * Definition for singly-linked list.
     * public class ListNode {
     * int val;
     * ListNode next;
     * ListNode() {}
     * ListNode(int val) { this.val = val; }
     * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     * }
     */
    class Solution {
        public boolean isPalindrome(ListNode head) {

            if (head.next == null)
                return true;
            ListNode temp = head;
            ArrayDeque<ListNode> deque = new ArrayDeque<>();
            while (temp != null) {
                deque.addLast(temp);
                temp = temp.next;
            }
            while (deque.size() > 1) {
                ListNode first = deque.removeFirst();
                ListNode last = deque.removeLast();
                if (first.val != last.val)
                    return false;
            }
            return true;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)


}
